/**1
3.2 线性表
顺序表
1. 实现顺序表的完整操作集，包括初始化、指定位置插入、指定位置删除、
按值查找（返回所有匹配索引）、获取指定位置元素、判空、求长度，
需处理越界插入、空表删除等异常（返回错误提示）。
测试用例：初始化容量为 5 的空表，
依次插入 1、2、3，在位置 2 插入 9，删除位置 3 的元素，最终表应为 [1,9,2]。
2. 设计有序顺序表（元素升序），实现 "插入元素保持有序" 和 "删除所有重复元素" 功能。
例如：向 [1,3,5] 插入 4 后变为 [1,3,4,5]；将 [2,2,3,3,3] 去重后变为 [2,3]。
3. 基于顺序表实现 "合并两个有序顺序表"：
输入两个升序顺序表 A 和 B，输出一个新的升序顺序表 C（包含 A 和 B 的所有元素）。
测试用例：A=[1,3,5]，B=[2,4,6]，输出C=[1,2,3,4,5,6]。

 */
#include <stdio.h>
#include <stdlib.h>

typedef struct SqList{
    int * data;
    int length;
    int capacity;
}SqList;
//--------------------------声明----------------------------------------
//初始化
SqList* initSqList(int capacity);
//判空
int isEmpty(SqList* list);
//求长度
int getLength(SqList* list);

// 指定位置插入（位置从1开始）第一个是data[0]
int insert_k(SqList* list,int k,int val);
//按值查找（返回所有匹配索引）、(返回所有匹配索引，索引从0开始）
void findAll(SqList* list,int val,int* result ,int* count);
//获取指定位置元素、（位置从1开始）第一个是data[0]
int get_k(SqList* list,int k);
// 打印顺序表
void printList(SqList *list);
void test1();
// 有序顺序表插入（保持升序）
int insertSorted(SqList *list, int value);
//删除所有重复元素(有序状态下)(重点---------！！！！！！！！！)
void removeDuplicates(SqList* list);
void test2();
//合并两个有序顺序表
SqList* mergeSortedLists(SqList *A, SqList *B);
//测试用例：A=[1,3,5]，B=[2,4,6]，输出C=[1,2,3,4,5,6]。
void test3();
//----------------------------------------------------------------------
//初始化
SqList* initSqList(int capacity){
    SqList* list = (SqList*)malloc(sizeof(SqList));
    list->data = (int*)malloc(sizeof(int)*capacity);
    list->length=0;
    list->capacity=capacity;
    return list;
}

//判空
int isEmpty(SqList* list){
    if(list==NULL){return -1;}
    return list->length==0;
}

//求长度
int getLength(SqList* list){
    if(list==NULL){return -1;}
    return list->length;
}

// 指定位置插入（位置从1开始）第一个是data[0]
int insert_k(SqList* list,int k,int val){
    if(list==NULL){return -1;}
    if(k>list->length+1 || k<1){return -1;}//不超过最后一个的后面
    if(list->capacity==list->length){return -2;}
    for(int i=list->length;i>=k;i--){
        list->data[i]=list->data[i-1];
    }
    list->data[k-1] = val;
    list->length++;
    return 0;
}

//指定位置删除 （位置从1开始）第一个是data[0]
int delet_k(SqList* list,int k){
    if(list==NULL){return -1;}
    if(list->length==0){return -1;}
    if(k>list->length || k<1){return -2;}

    for(int i=k;i<list->length;i++){
        list->data[i-1]=list->data[i];//写i-1比i+1要好
    }
    list->length--;
    return 0;
}
//按值查找（返回所有匹配索引）、(返回所有匹配索引，索引从0开始）
void findAll(SqList* list,int val,int* result ,int* count){
    if(list==NULL){return ;}
    if(list->length==0){return ;}
    *count = 0;
    for(int i=0;i<list->length;i++){
        if(list->data[i]==val){
            result[*count]=i;
            (*count)++;
        }
    }
}
//获取指定位置元素、（位置从1开始）第一个是data[0]
int get_k(SqList* list,int k){
    if(isEmpty(list)){return -1;}
    if(k>list->length || k<1){return -2;}
    return list->data[k-1];
}
// 打印顺序表
void printList(SqList *list) {
    printf("[");
    for (int i = 0; i < list->length; i++) {
        printf("%d", list->data[i]);
        if (i != list->length - 1) {
            printf(",");
        }
    }
    printf("]\n");
}
/**测试用例：初始化容量为 5 的空表，
依次插入 1、2、3，在位置 2 插入 9，删除位置 3 的元素，最终表应为 [1,9,2]。 */
void test1(){
    SqList *list =initSqList(5);
    //依次插入 1、2、3
    insert_k(list,1,1);
    insert_k(list,2,2);
    insert_k(list,3,3);
    printf("依次插入 1、2、3，在位置 2 插入 9，删除位置 3 的元素，最终表应为 [1,9,2]\n");
    printList(list);
    //在位置 2 插入 9
    insert_k(list,2,9);
    //删除位置 3 的元素
    delet_k(list,3);
    printList(list);
}

/**2. 设计有序顺序表（元素升序），实现 "插入元素保持有序" 和 "删除所有重复元素" 功能。
例如：向 [1,3,5] 插入 4 后变为 [1,3,4,5]；将 [2,2,3,3,3] 去重后变为 [2,3]。 */

// 有序顺序表插入（保持升序）
int insertSorted(SqList *list, int value) {
    if (list->length >= list->capacity) {
        return -1;  // 表已满
    }
    
    // 查找插入位置
    int i = 0;
    while (i < list->length && list->data[i] < value) {
        i++;
    }
    // 插入操作
    return insert_k(list, i + 1, value);
}
//删除所有重复元素(有序状态下)(重点---------！！！！！！！！！)
void removeDuplicates(SqList* list){
    if(isEmpty(list)){return ;}
    if(list->length==1){return ;}
    int i=0;
    for(int j = 1;j <list->length;j++){
        if(list->data[i]!=list->data[j]){//(重点---------！！！！！！！！！)
            i++;
            list->data[i]=list->data[j];
        }
    }
    list->length=i+1;
}
//例如：向 [1,3,5] 插入 4 后变为 [1,3,4,5]；将 [2,2,3,3,3] 去重后变为 [2,3]。 */
void test2(){
    printf("向 [1,3,5] 插入 4 后变为 [1,3,4,5]\n");
    SqList* list =initSqList(10);
    insertSorted(list,1);
    insertSorted(list,3);
    insertSorted(list,5);
    printList(list);
    insertSorted(list,4);
    printf("将 [2,2,3,3,3] 去重后变为 [2,3]。\n");
    list=initSqList(10);
    insert_k(list,1,2);
    insert_k(list,2,2);
    insert_k(list,3,3);
    insert_k(list,4,3);
    insert_k(list,5,3);
    printList(list);
    removeDuplicates(list);
}

/**3. 基于顺序表实现 "合并两个有序顺序表"：
输入两个升序顺序表 A 和 B，输出一个新的升序顺序表 C（包含 A 和 B 的所有元素）。
测试用例：A=[1,3,5]，B=[2,4,6]，输出C=[1,2,3,4,5,6]。
 */
//合并两个有序顺序表
SqList* mergeSortedLists(SqList *A, SqList *B) {
    SqList *C = initSqList(A->length+B->length);
    C->length=0;
    int i=0,j=0,k=0;
    while(i<A->length && j<B->length){
        if( A->data[i]<B->data[j]){
            C->data[k] = A->data[i];
            k++;
            i++;
        }else{
                C->data[k] = B->data[j];
                k++;
                j++;
        }
    
    }
    while(i<A->length){
        C->data[k++]=A->data[i++];
    }
    while(j<B->length){
        C->data[k++]=B->data[j++];
    }
    C->length=k;
    return C;

}
//测试用例：A=[1,3,5]，B=[2,4,6]，输出C=[1,2,3,4,5,6]。
void test3(){
    SqList* A =initSqList(3);
    SqList* B =initSqList(3);
    insert_k(A,1,1);
    insert_k(A,2,3);
    insert_k(A,3,5);
    insert_k(B,1,2);
    insert_k(B,2,4);
    insert_k(B,3,6);
    printList(A);
    printList(B);
    printf("合并\n");
    printList( mergeSortedLists(A,B));
}
int main(){
    printf("-------1---------\n");
    test1();
        printf("---------2----------\n");
    test2();
        printf("--------3----------\n");
    test3();
    return 0;

}

